/*
 * isWin standalone program
 * Author: Travis Danniels
 */ 

#include "isWin.h"

/* 
 * main reads an argument from STDIN in the exact format described above in the
 * PROGRAM INPUT section of the header, and 
 * returns the 'win value' of the input from red's perspective 
 * (i.e 5 if red has something like rrgg, -5 if blue has something like 
 * bbgg, etc.)
 */

extern int rows;
extern int cols;
extern int last_move;
extern int total_time;
extern int player_1_time;
extern int last_move_time;

// LSB (0):NW, (1):N, (2):NE, (3):E bit is 0 if not scanned, 1 otherwise
static int *scanHash;

static int rwinc;
static int bwinc;
static int rwins[7];
static int bwins[7];

// foundWin: Set to 1 upon encountering a winning run
static int foundWin;

int isWin ( char *board )
{
    int i, j;
    int val;

    rwinc = 0;
    bwinc = 0;
    foundWin = 0;

    scanHash = malloc ( sizeof(int) * cols * rows);
    for ( i = 0; i < cols; i++ )
        for ( j = 0; j < rows; j++ )
            scanHash[i + j*cols] = 0;

#if DBG
// print board to verify
    for (j = rows - 1; j >= 0; j--)
       for (i = 0; i < cols; i++) {
          printf("%c", CELL(board,i,j,cols) );
          if (i == cols - 1)
              printf("\n");
       }
    printf("\n");
#endif

    // Scan on a column-major order so that when we can break
    // upon encountering an empty space
    for ( i = 0; i < cols; i++ ) {
        for ( j = 0; j < rows; j++ ) {
            switch ( CELL(board,i,j,cols) ) {
                case 'g':
                    if ( (val = scanCell ( i, j, board ) ) ) {
                        free ( scanHash );
//                        printf("WIN:%d\n",val);
                        return val;
                    }
                    break;
                case 's':
                    j = rows;
                    break;
                default :
                    break;
            }
        }
    }
    // No win
    free ( scanHash );
    // Full board tie?
    if ( (i == cols) && (j == rows) )
        return 1;
    else
        return 0;
}

int scanCell ( int x, int y, char *board )
{
#if DEBUG
    printf("Scanning (%d,%d)\n", x, y);
#endif
    int boardVal;
    
    // Horizontal from left to right
    if ( (boardVal = scanEast ( x, y, board)) )
        return boardVal;
    if ( (boardVal = scanNorthEast ( x, y, board)) )
        return boardVal;
    if ( (boardVal = scanNorthWest ( x, y, board)) )
        return boardVal;
    if ( (boardVal = scanNorth ( x, y, board)) )
        return boardVal;
    // This cell is not a part of any winning runs
    return 0;
}

int scanEast ( int x, int y, char *board )
{   
#if DEBUG3
    printf("scanEast: (%d,%d)\n",x,y);
#endif
    int i, r;
    int min_i;
    int max_i; 
    int bc;
    int gc;
    int rc;
    char run[4];
    int run_coords[8]; //x0 x1 x2 x3 y0 y1 y2 y3

    // Horizontal from left to right
    min_i  = x - 3;
    if ( x < 3 )
        min_i = 0;

    max_i = x;
    if ( x > cols - 4 )
        max_i = cols - 4;

    for ( i = min_i; i <= max_i; i++ ) {
        // Skip this run if it has already been checked
        if ( HASHED(scanHash,i,y,EAST,cols) )
            continue;
        // Now we are checking it, so hash it
        SETHASH(scanHash,i,y,EAST,cols);
        bc = gc = rc = 0;
        for ( r = i; r < i + 4; r++ ) {
            switch CELL(board,r,y,cols) {
                case 'b':
                    bc++;
                    break;
                case 'g':
                    gc++;
                    break;
                case 'r':
                    rc++;
                    break;
                default : 
                    break;
            }
        }
        // Do we have a winner?
        if ( ( gc ==  2 ) && ( ( rc == 2 ) || ( bc == 2 ) ) ) {
#if DEBUG3
            printf("scanEast found win starting at (%d,%d)\n", i, y);
#endif           
            for ( r = i; r < i + 4; r++ )
                run[r-i] = CELL(board,r,y,cols);
            if ( rc == 2 ) {
                rwins[rwinc] = getRunValue ( run );
                rwinc++;
                // If we were called by verifyWin, keep going until
                // all runs have been checked
                if ( foundWin )
                    continue; 
            } else {
                bwins[bwinc] = getRunValue ( run );
                bwinc++;
                if ( foundWin )
                    continue;
            }
            // Now verify the winning run by checking each of the squares
            // that compose it for membership in other winning runs.
            // These following calls should only ever be made _once_ (or never)

		//	run_coords = {i, i+1, i+2, i+3, y, y, y, y};
			run_coords[0] = i;
			run_coords[1] = i+1;
			run_coords[2] = i+2;
			run_coords[3] = i+3;
			run_coords[4] = y;
			run_coords[5] = y;
			run_coords[6] = y;
			run_coords[7] = y;

            foundWin = 1;
            return verifyWin ( board, run_coords );
        }
    } // End horizontal from left to right
    return 0;
}



int scanNorth ( int x, int y, char *board  )
{   
    int i, r;
    int min_i;
    int max_i; 
    int bc;
    int gc;
    int rc;
    char run[4];
    int run_coords[8]; //x0 x1 x2 x3 y0 y1 y2 y3

    // Vertical from South to North
    min_i  = y - 3;
    if ( y < 3 )
        min_i = 0;

    max_i = y;
    if ( y > rows - 4 )
        max_i = rows - 4;

    for ( i = min_i; i <= max_i; i++ ) {
        // Skip this run if it has already been checked
        if ( HASHED(scanHash,x,i,NORTH,cols) )
            continue;
        // Now we are checking it, so hash it
        SETHASH(scanHash,x,i,NORTH,cols);
        bc = gc = rc = 0;
        for ( r = i; r < i + 4; r++ ) {
            switch CELL(board,x,r,cols) {
                case 'b':
                    bc++;
                    break;
                case 'g':
                    gc++;
                    break;
                case 'r':
                    rc++;
                    break;
                default : 
                    break;
            }
        }
        // Do we have a winner?
        if ( ( gc ==  2 ) && ( ( rc == 2 ) || ( bc == 2 ) ) ) {
            for ( r = i; r < i + 4; r++ )
                run[r-i] = CELL(board,x,r,cols);
            if ( rc == 2 ) {
                rwins[rwinc] = getRunValue ( run );
                rwinc++;
                // If we were called by verifyWin, keep going until
                // all runs have been checked
                if ( foundWin )
                    continue; 
            } else {
                bwins[bwinc] = getRunValue ( run );
                bwinc++;
                if ( foundWin )
                    continue;

            }
            // Now verify the winning run by checking each of the squares
            // that compose it for membership in other winning runs.
            // These following calls should only ever be made _once_ (or never)
            //run_coords = {x, x, x, x, i, i+1, i+2, i+3};

			run_coords[0] = x;
			run_coords[1] = x;
			run_coords[2] = x;
			run_coords[3] = x;
			run_coords[4] = i;
			run_coords[5] = i+1;
			run_coords[6] = i+2;
			run_coords[7] = i+3;

            foundWin = 1;
            return verifyWin ( board, run_coords );
        }
    } // End vertical from South to North
    return 0;
}



int scanNorthEast ( int  x, int  y, char *board )
{
#if DEBUG
    printf("entered scanNorthEast\n");
#endif
    int i, j, r, s;
    int min_i;
    int max_i;
    int min_j;
    int max_j; 
    int bc;
    int gc;
    int rc;
    char run[4];
    int run_coords[8]; //x0 x1 x2 x3 y0 y1 y2 y3

    // Diagonal from bottom left to top right

    // First get the x boundaries
    for ( r = 0; r < 4; r++) {
        if ( (x - r >= 0) && (y - r >= 0) ) {
            min_i = x - r;
            min_j = y - r;
        }
    }
    max_i = x;
    if ( x > cols - 4 )
        max_i = cols - 4;

    // And then the y boundaries
    max_j = y;
    if (y > rows - 4 )
        max_j = rows - 4;

    i = min_i;
    j = min_j;
#if DEBUG
        printf("scanNorthEast: min_i = %d, max_i = %d, min_j = %d,"
               " max_j = %d\n", min_i, max_i, min_j, max_j);
#endif
    while ( (i <= max_i) && (j <= max_j) ) {
#if DEBUG
        printf("scanNorthEast: (i,j) = (%d,%d)\n", i, j);
#endif
        // Skip this run if it has already been checked
        if ( HASHED(scanHash,i,j,NORTHEAST,cols) ) {
#if DEBUG
            printf("scanNorthEast: skipping (i,j) = (%d,%d)\n", i, j);
#endif
            i++;
            j++;
            continue;
        }
        // Now we are checking it, so hash it
        SETHASH(scanHash,i,j,NORTHEAST,cols);
        bc = gc = rc = 0;
        r = i;
        s = j;
        while ( ( r < i + 4) && ( s < j + 4 ) ) {

#if DEBUG
           printf("scanNorthEast: cell(board,%d,%d,cols) = %c\n", r, s,CELL(board,r,s,cols) );
#endif
            switch CELL(board,r,s,cols) {
                case 'b':
                    bc++;
                    break;
                case 'g':
                    gc++;
                    break;
                case 'r':
                    rc++;
                    break;
                default : 
                    break;
            }
            r++;
            s++;
        }
#if DEBUG
        printf("scanNorthEast: bc = %d, gc = %d, rc = %d\n", bc, gc, rc);
#endif
        // Do we have a winner?   

        if ( ( gc ==  2 ) && ( ( rc == 2 ) || ( bc == 2 ) ) ) {
            r = i;
            s = j;
            while ( ( r < i + 4) && ( s < j + 4 ) ) {
                run[r-i] = CELL(board,r,s,cols);
                r++;
                s++;
            }
            if ( rc == 2 ) {
                rwins[rwinc] = getRunValue ( run );
                rwinc++;
                // If we were called by verifyWin, keep going until
                // all runs have been checked
                if ( foundWin )
                    continue; 
            } else {
                bwins[bwinc] = getRunValue ( run );
                bwinc++;
                if ( foundWin )
                    continue;
            }
            // Now verify the winning run by checking each of the squares
            // that compose it for membership in other winning runs.
            // These following calls should only ever be made _once_ (or never)
            //run_coords = {i, i+1, i+2, i+3, j, j+1, j+2, j+3};

			run_coords[0] = i;
			run_coords[1] = i+1;
			run_coords[2] = i+2;
			run_coords[3] = i+3;
			run_coords[4] = j;
			run_coords[5] = j+1;
			run_coords[6] = j+2;
			run_coords[7] = j+3;

            foundWin = 1;
            return verifyWin ( board, run_coords );
        }
        i++;
        j++;
    } // End diagonal from bottom left to top right
    return 0;
}


int scanNorthWest ( int x, int y, char *board )
{
#if DEBUG2
    printf("entered scanNorthWest (%d,%d)\n",x,y);
#endif
    int i, j, r, s;
    int min_i;
    int max_i;
    int min_j;
    int max_j; 
    int bc;
    int gc;
    int rc;
    char run[4];
    int run_coords[8]; //x0 x1 x2 x3 y0 y1 y2 y3

    // Diagonal from bottom right to top left
    // First get the x boundaries

    min_i  = x;
    if ( x < 3 )
        min_i = 3;

    for ( r = 0; r < 4; r++) {
        if ( (x + r <= cols - 1) && (y - r >= 0) ) {
            max_i = x + r;
            min_j = y - r;
        }
    }
    // And then the y boundaries
    max_j = y;
    if (y > rows - 4 )
        max_j = rows - 4;

    i = max_i;
    j = min_j;
#if DEBUG2
    printf("scanNorthWest: min_i = %d, max_i = %d, min_j = %d,"
           " max_j = %d\n", min_i, max_i, min_j, max_j);
#endif
    while ( (i >=min_i) && (j <= max_j) ) {
#if DEBUG2
        printf("scanNorthWest: (i,j) = (%d,%d)\n", i, j);
#endif

        // Skip this run if it has already been checked
        if ( HASHED(scanHash,i,j,NORTHWEST,cols) ) {
#if DEBUG2
            printf("scanNorthWest: skipping (i,j) = (%d,%d)\n", i, j);
#endif
            i--;
            j++;
            continue;
        }
        // Now we are checking it, so hash it
        SETHASH(scanHash,i,j,NORTHWEST,cols);
        bc = gc = rc = 0;
        //for ( r = i; r < i + 4; r++ ) {
        r = i;
        s = j;
        while ( ( r >= i - 3) && ( s < j + 4 ) ) {
#if DEBUG2
            printf("scanNorthWest: cell(board,%d,%d,cols) = %c\n", r, s,CELL(board,r,s,cols) );
#endif

            switch CELL(board,r,s,cols) {
                case 'b':
                    bc++;
                    break;
                case 'g':
                    gc++;
                    break;
                case 'r':
                    rc++;
                    break;
                default : 
                    break;
            }
            r--;
            s++;
        }
#if DEBUG2
        printf("scanNorthWest: bc = %d, gc = %d, rc = %d\n", bc, gc, rc);
#endif
        // Do we have a winner?   

        if ( ( gc ==  2 ) && ( ( rc == 2 ) || ( bc == 2 ) ) ) {
#if DEBUG3
            printf("scanNorthWest found win starting at (%d,%d)\n", i, j);
#endif
            r = i;
            s = j;
            while ( ( r >= i - 3) && ( s < j + 4 ) ) {
                run[s-j] = CELL(board,r,s,cols);
                r--;
                s++;
            }
            if ( rc == 2 ) {
                rwins[rwinc] = getRunValue ( run );
                rwinc++;
                // If we were called by verifyWin, keep going until
                // all runs have been checked
                if ( foundWin )
                    continue; 
            } else {
                bwins[bwinc] = getRunValue ( run );
                bwinc++;
                if ( foundWin )
                    continue;
            }
            // Now verify the winning run by checking each of the squares
            // that compose it for membership in other winning runs.
            // These following calls should only ever be made _once_ (or never)
            //run_coords = {i+3, i+2, i+1, i, j, j+1, j+2, j+3};

			run_coords[0] = i;
			run_coords[1] = i-1;
			run_coords[2] = i-2;
			run_coords[3] = i-3;
			run_coords[4] = j;
			run_coords[5] = j+1;
			run_coords[6] = j+2;
			run_coords[7] = j+3;

            foundWin = 1;
            return verifyWin ( board, run_coords );
        }
        i--;
        j++;
#if DEBUG
        printf("scanNorthWest: exiting ij while loop\n");
#endif
    } // End diagonal from bottom left to top right
    return 0;
}


int getRunValue ( char *run )
{
    int rv;
    // Type-1 win
    if ( run[0] == run[1] ) {
        rv = 5;
        if ( ( run[0] == 'b' ) || ( run[2] == 'b' ) )
            rv *= -1;
        return rv;
    }
    // Type-2 win
    if ( run[0] == run[3] ) {
        rv = 4;
        if ( ( run[0] == 'b' ) || ( run[1] == 'b' ) )
            rv *= -1;
        return rv;
    }
    // Type-3 win
    if ( run[0] == run[2] ) {
        rv = 3;
        if ( ( run[0] == 'b' ) || ( run[1] == 'b' ) )
            rv *= -1;
        return rv;
    }
    // This should not happen!
    //printf ("error -- non-winning run passed to getRunValue\n");
    return 0;
}

int verifyWin ( char *board, int *run_coords )
{
#if DEBUG3
    printf("Entered verifyWin\n");
    printf("run_coords = { (%d,%d), (%d,%d), (%d,%d), (%d,%d) }\n",
            run_coords[0],run_coords[4],run_coords[1],run_coords[5],
            run_coords[2],run_coords[6],run_coords[3],run_coords[7]);
#endif
    int i;
    int rTotal = 0;
    int bTotal = 0;
    int rMax = 0;
    int bMin = 0;

    for ( i = 0; i < 4; i++ ) {
#if DEBUG
    printf("verifyWin: scanning NW\n");
#endif       
        scanNorthWest ( run_coords[i], run_coords[i+4], board );
#if DEBUG
    printf("verifyWin: scanning N\n");
#endif       
        scanNorth ( run_coords[i], run_coords[i+4], board );
#if DEBUG
    printf("verifyWin: scanning NE\n");
#endif       
        scanNorthEast ( run_coords[i], run_coords[i+4], board );
#if DEBUG
    printf("verifyWin: scanning E\n");
#endif       
        scanEast ( run_coords[i], run_coords[i+4], board );
    }
    for ( i = 0; i < rwinc; i++ ) {
        rTotal += rwins[i];
        if ( rwins[i] > rMax )
            rMax = rwins[i];
    }
    for ( i = 0; i < bwinc; i++ ) {
        bTotal += bwins[i];
        if ( bwins[i] < bMin )
            bMin = bwins[i];
    }
#if DEBUG
    printf("rwinc = %d, bwinc = %d\n", rwinc, bwinc);
    printf("rTotal = %d\nrMax = %d\nbTotal = %d\nbMin = %d\n",
            rTotal, rMax, bTotal, bMin);
#endif
    if ( rTotal > (-1 * bTotal) ) {
        return rMax;
    } else if ( rTotal < (-1 * bTotal) ) {
        return bMin;
    } else
        return 1;
}
